package org.basis.algorithm.sort;

import java.util.*;

/**
 * 并查集
 */
public class UnionFind {
    private HashMap<Node, Node> fatherMap;
    private HashMap<Node, Integer> rankMap;
    private Integer distance;

    /**
     * 初始化并查集
     */
    public UnionFind(Integer distance) {
        fatherMap = new HashMap<>();
        rankMap = new HashMap<>();
        this.distance = distance;
    }

    public static void main(String[] args) {
        // 准备好1000个点
        List<Node> nodes = new ArrayList<>();
        nodes.add(new Node(0));
        nodes.add(new Node(1));
        nodes.add(new Node(2));
        nodes.add(new Node(3));
        nodes.add(new Node(7));
        nodes.add(new Node(8));
        // 距离
        final int distance = 1;
        UnionFind unionFind = new UnionFind(distance);
        // 初始化并查集
        unionFind.makeSets(nodes);
        // 遍历每一个节点
        for (int i = 0; i < nodes.size(); i++) {
            for (int j = i; j < nodes.size(); j++) {
                // 进行合并
                unionFind.union(nodes.get(i), nodes.get(j));
            }
        }

        // 每个头就是一个簇
        HashMap<Node, List<Node>> map = new HashMap<>();
        unionFind.fatherMap.forEach((k, v) -> {
            List<Node> list = map.get(v);
            if (list == null) {
                list = new ArrayList<>();
                map.put(v, list);
            }
            list.add(k);
        });

        map.forEach((k, v) -> {
            System.out.println("key = " + k + " value = " + v);
        });

    }

    /**
     * 找到node的头节点
     */
    private Node findFather(Node n) {
        Node father = fatherMap.get(n);
        if (father != n) {
            father = findFather(father);
        }
        fatherMap.put(n, father);
        return father;
    }

    public void makeSets(Collection<Node> nodes) {
        fatherMap.clear();
        rankMap.clear();
        for (Node node : nodes) {
            fatherMap.put(node, node);
            rankMap.put(node, 1);
        }
    }

    /**
     * 三两个点是否属于同一个集合
     */
    public boolean isSameSet(Node a, Node b) {
        return findFather(a) == findFather(b);
    }

    /**
     * 快速合并
     */
    public void union(Node a, Node b) {
        if (a == null || b == null) {
            return;
        }
        Node aFather = findFather(a);
        Node bFather = findFather(b);
        // 如果属于同一个头，则说明已经在同一个集合中
        if (aFather != bFather && distance(a, b) <= distance) {
            int aFrank = rankMap.get(aFather);
            int bFrank = rankMap.get(bFather);
            // 合并集合，小的往大的上面合
            if (aFrank <= bFrank) {
                fatherMap.put(aFather, bFather);
                rankMap.put(bFather, aFrank + bFrank);
            } else {
                fatherMap.put(bFather, aFather);
                rankMap.put(aFather, aFrank + bFrank);
            }
        }
    }

    /**
     * 求两点之间的距离
     */
    private int distance(Node node1, Node node2) {
        Integer a = node1.getX() - node2.getX();

        // todo 由求距离公式实现
        return getAbsolute(a);
    }

    static class Node {
        public Integer x;
        public Integer y;

        public Node(Integer x) {
            this.x = x;
        }

        public Node(Integer x, Integer y) {
            this.x = x;
            this.y = y;
        }


        public Integer getX() {
            return x;
        }

        public void setX(Integer x) {
            this.x = x;
        }

        public Integer getY() {
            return y;
        }

        public void setY(Integer y) {
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }
            Node node = (Node) o;
            return Objects.equals(x, node.x) &&
                    Objects.equals(y, node.y);
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }

    public int getAbsolute(int a) {
        return a * (1 - ((a >>> 31) << 1));
    }
}